
我们在上一节中构建的解析器只检查输入的语法，下一步是添加执行语义分析的能力。上一章的calc示例中，解析器构建了一个AST。在另一个单独的阶段中，语义分析器在这个树上工作。这种方法总是可以使用的。本节中，我们将使用一种稍微不同的方法，并将解析器和语义分析器更多地交织在一起。

语义分析器需要做什么?一起来看看:

\begin{itemize}
\item
对于每个声明，必须检查变量、对象等的名称，以确保它们没有在其他地方声明过。

\item
对于表达式或语句中每次出现的名称，必须检查是否声明了该名称，以及所需的用途是否符合声明。

\item
对于每个表达式，必须计算结果类型。还需要计算表达式是否为常量，若是常量，具为哪个值。

\item
对于赋值和形参传递，必须检查类型是否兼容。此外，必须检查IF和WHILE语句中的条件是否为BOOLEAN类型。
\end{itemize}

对于这样一个编程语言的小子集来说，要检查的东西已经很多了!

\mySubsubsection{3.7.1.}{处理名称作用域}

先来了解一下名称作用域，名称作用域是该名称可见的范围。与C语言一样，tinylang使用了使用前声明(declare-before-use)模型。例如，B和X变量在模块级别可声明为INTEGER类型:

\begin{shell}
VAR B, X: INTEGER;
\end{shell}

声明之前，变量是未知的，不能使用。这只有在声明之后才有可能。在一个过程中，可以声明更多的变量:

\begin{shell}
PROCEDURE Proc;
VAR B: BOOLEAN;
BEGIN
    (* Statements *)
END Proc;
\end{shell}

注释所在的位置，使用B指向B局部变量，而使用X指向X全局变量。局部变量B的作用域是Proc。若在当前作用域中找不到名称，则在外层封闭作用域中继续搜索，所以X变量可以在过程中使用。在tinylang中，只有模块和过程打开一个新的作用域。其他语言结构，如结构和类，通常也会打开作用域。预定义实体，如INTEGER类型和TRUE在全局作用域中声明，包含模块的作用域。

在tinylang中，只有名字才是关键。可以将作用域实现为从名称到其声明的映射，只有在新名称不存在的情况下才能插入该名称。对于查找，还必须知道封闭或父作用域，接口(在include/tinylang/Sema/Scope.h文件中)如下所示:

\begin{cpp}
#ifndef TINYLANG_SEMA_SCOPE_H
#define TINYLANG_SEMA_SCOPE_H

#include "tinylang/Basic/LLVM.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"

namespace tinylang {

class Decl;

class Scope {
    Scope *Parent;
    StringMap<Decl *> Symbols;

    public:
    Scope(Scope *Parent = nullptr) : Parent(Parent) {}

    bool insert(Decl *Declaration);
    Decl *lookup(StringRef Name);

    Scope *getParent() { return Parent; }
};
} // namespace tinylang
#endif
\end{cpp}

lib/Sema/Scope.cpp文件中的实现如下所示:

\begin{cpp}
#include "tinylang/Sema/Scope.h"
#include "tinylang/AST/AST.h"

using namespace tinylang;

bool Scope::insert(Decl *Declaration) {
    return Symbols
        .insert(std::pair<StringRef, Decl *>(
            Declaration->getName(), Declaration))
        .second;
}
\end{cpp}

注意，StringMap::insert()方法不会覆盖现有条目。结果std::pair的第二个成员表示表是否更新，此信息将返回给调用者。

要实现对符号声明的搜索，lookup()方法在当前作用域内搜索，若没有找到，则搜索父成员链接的作用域:

\begin{cpp}
Decl *Scope::lookup(StringRef Name) {
    Scope *S = this;
    while (S) {
        StringMap<Decl *>::const_iterator I =
            S->Symbols.find(Name);
        if (I != S->Symbols.end())
            return I->second;
        S = S->getParent();
    }
    return nullptr;
}
\end{cpp}

然后，对变量声明进行如下处理:

\begin{itemize}
\item
当前的作用域是模块作用域。

\item
查找INTEGER类型声明。若没有找到声明或者不是类型声明，则会出现错误。

\item
实例化一个名为VariableDeclaration的新AST节点，其中重要的属性是名称B和类型。

\item
名称B插入到当前作用域，映射到声明实例。若该名称已经存在于作用域中，则这是一个错误，所以当前作用域的内容不会改变。

\item
对于X变量也是如此。
\end{itemize}

这里执行两个任务。与calc示例一样，构造AST节点。同时，计算节点的属性，如类型。为什么这是可能的呢?

语义分析器可以依赖于两组不同的属性：作用域继承自调用者，类型声明可以通过评估类型声明中的名称来计算(或者说合成)。该语言的设计方式，使得这两组属性足以计算AST节点的所有属性。

这里，需要先声明再使用模型。若一种语言允许在声明之前使用名称，例如C++中类中的成员，不可能一次计算一个AST节点的所有属性，AST节点必须仅使用部分计算的属性或仅使用普通信息(例如在calc示例中)来构造。

然后必须访问AST一次或多次以确定缺失的信息。在tinylang(和Modula-2)的情况下，可以省去AST构造——AST是通过parseXXX()方法的调用层次结构间接表示。使用AST生成代码更为常见，所以我们在这里也构造一个AST。

在把这些部分放在一起之前，我们需要了解LLVM使用运行时类型信息(runtime type information, RTTI)的风格。

\mySubsubsection{3.7.2.}{使用LLVM风格RTTI的AST}

当然，AST节点是类层次结构的一部分。声明总是有一个名称，其他属性取决于所声明的内容。若声明了变量，则需要指定类型。声明常量需要类型、值等。在运行时，需要找出使用的是哪种类型的声明，dynamic\_cast<>的C++操作符可用于此。问题是，只有当C++类附加了虚函数表时，所需的RTTI才可用——使用了虚函数。另一个缺点是C++ RTTI过于臃肿。为了避免这些缺点，LLVM开发人员引入了一种自制的RTTI风格，这种风格在整个LLVM库中使用。

我们的层次结构的(抽象)基类是Decl，要实现llvm风格的RTTI，必须添加一个公共枚举，其中包含每个子类的标签。此外，还需要该类型的私有成员和公共getter。私有成员通常为Kind。具体的实现，如下所示:

\begin{cpp}
class Decl {
public:
    enum DeclKind { DK_Module, DK_Const, DK_Type,
        DK_Var, DK_Param, DK_Proc };
private:
    const DeclKind Kind;
public:
    DeclKind getKind() const { return Kind; }
};
\end{cpp}

现在，每个子类都需要一个名为classof的特殊函数成员。该函数的目的是确定给定实例是否属于所请求的类型。对于VariableDeclaration，实现如下:

\begin{cpp}
static bool classof(const Decl *D) {
    return D->getKind() == DK_Var;
}
\end{cpp}

现在，可以使用特殊模板llvm::isa<>来检查对象是否为所请求的类型，并使用llvm::dyn\_cast<>来动态转换对象。存在更多模板，但这两个是最常用的模板。有关其他模板，请参阅\url{https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates};有关LLVM样式的更多信息，包括更高级的用法，请参阅\url{https://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html}。

\mySubsubsection{3.7.3.}{创建语义分析器}

有了这些，现在可以实现所有的部分。首先，必须为存储在include/llvm/tinylang/AST/AST.h文件中的变量创建AST节点的定义。除了支持LLVM风格的RTTI，基类存储声明的名称、名称的位置和一个指向外层声明的指针，后者在嵌套过程的代码生成过程中是必需的。Decl基类声明如下:

\begin{cpp}
class Decl {
public:
    enum DeclKind { DK_Module, DK_Const, DK_Type,
                    DK_Var, DK_Param, DK_Proc };

private:
    const DeclKind Kind;

protected:
    Decl *EnclosingDecL;
    SMLoc Loc;
    StringRef Name;

public:
    Decl(DeclKind Kind, Decl *EnclosingDecL, SMLoc Loc,
        StringRef Name)
        : Kind(Kind), EnclosingDecL(EnclosingDecL), Loc(Loc),
        Name(Name) {}

    DeclKind getKind() const { return Kind; }
    SMLoc getLocation() { return Loc; }
    StringRef getName() { return Name; }
    Decl *getEnclosingDecl() { return EnclosingDecL; }
};
\end{cpp}

变量的声明只向类型声明添加一个指针:

\begin{cpp}
class TypeDeclaration;

class VariableDeclaration : public Decl {
    TypeDeclaration *Ty;

public:
    VariableDeclaration(Decl *EnclosingDecL, SMLoc Loc,
                        StringRef Name, TypeDeclaration *Ty)
        : Decl(DK_Var, EnclosingDecL, Loc, Name), Ty(Ty) {}

    TypeDeclaration *getType() { return Ty; }

    static bool classof(const Decl *D) {
        return D->getKind() == DK_Var;
    }
};
\end{cpp}

解析器中的方法需要扩展语义动作和收集信息的变量:

\begin{cpp}
bool Parser::parseVariableDeclaration(DeclList &Decls) {
    auto _errorhandler = [this] {
        while (!Tok.is(tok::semi)) {
            advance();
            if (Tok.is(tok::eof)) return true;
        }
        return false;
    };

    Decl *D = nullptr; IdentList Ids;
    if (parseIdentList(Ids)) return _errorhandler();
    if (consume(tok::colon)) return _errorhandler();
    if (parseQualident(D)) return _errorhandler();
    Actions.actOnVariableDeclaration(Decls, Ids, D);
    return false;
}
\end{cpp}

DeclList是声明列表，std::vector<Decl*>和IdentList是位置和标识符列表，std::vector<std::pair<SMLoc, StringRef>{}>。

parseQualident()方法返回一个声明，在本例中应该是一个类型声明。

解析器类知道存储在Actions成员中的语义分析器类Sema的实例。对actOnVariableDeclaration()的调用运行语义分析器和AST构造，实现在lib/Sema/Sema.cpp文件中:

\begin{cpp}
void Sema::actOnVariableDeclaration(DeclList &Decls,
IdentList &Ids,
Decl *D) {
    if (TypeDeclaration *Ty = dyn_cast<TypeDeclaration>(D)) {
        for (auto &[Loc, Name] : Ids) {
            auto *Decl = new VariableDeclaration(CurrentDecl, Loc,
            Name, Ty);
            if (CurrentScope->insert(Decl))
                Decls.push_back(Decl);
            else
                Diags.report(Loc, diag::err_symbold_declared, Name);
        }
    } else if (!Ids.empty()) {
        SMLoc Loc = Ids.front().first;
        Diags.report(Loc, diag::err_vardecl_requires_type);
    }
}
\end{cpp}

使用llvm::dyn\_cast<TypeDeclaration>检查类型声明。若不是类型声明，则打印错误消息；否则，对于Ids列表中的每个名称，将实例化VariableDeclaration并添加到声明列表中。若将变量添加到当前作用域中失败，因为变量名已经声明，也会输出一条错误消息。

大多数其他实体以相同的方式构建——语义分析的复杂性是唯一的区别。模块和过程需要做更多的工作，打开了一个新的作用域。打开一个新的作用域很容易:只需要实例化一个新的作用域对象。在解析模块或过程之后，必须删除作用域。

这一类实现必须可靠，我们不想在出现语法错误时将名称添加到错误的作用域中，这是C++中资源获取即初始化(Resource Acquisition Is Initialization, RAII)习惯用法的经典用法。另一个复杂之处在于过程可以递归地调用自身，所以在使用过程之前，必须将其名称添加到当前作用域。语义分析器有两个方法来进入和离开作用域。作用域与声明相关联:

\begin{cpp}
void Sema::enterScope(Decl *D) {
    CurrentScope = new Scope(CurrentScope);
    CurrentDecl = D;
}

void Sema::leaveScope() {
    Scope *Parent = CurrentScope->getParent();
    delete CurrentScope;
    CurrentScope = Parent;
    CurrentDecl = CurrentDecl->getEnclosingDecl();
}
\end{cpp}

一个简单的辅助类用于实现RAII惯用法:

\begin{cpp}
class EnterDeclScope {
    Sema &Semantics;

public:
    EnterDeclScope(Sema &Semantics, Decl *D)
    : Semantics(Semantics) {
        Semantics.enterScope(D);
    }
    ~EnterDeclScope() { Semantics.leaveScope(); }
};
\end{cpp}

解析模块或过程时，语义分析器会进行两次交互。第一个是在名字被解析之后，构造了(几乎是空的)AST节点，并建立了一个新的作用域:

\begin{cpp}
bool Parser::parseProcedureDeclaration(/* … */) {
    /* … */
    if (consume(tok::kw_PROCEDURE)) return _errorhandler();
    if (expect(tok::identifier)) return _errorhandler();
    ProcedureDeclaration *D =
        Actions.actOnProcedureDeclaration(
            Tok.getLocation(), Tok.getIdentifier());
    EnterDeclScope S(Actions, D);
    /* … */
}
\end{cpp}

语义分析器检查当前范围中的名称，返回AST节点:

\begin{cpp}
ProcedureDeclaration *
Sema::actOnProcedureDeclaration(SMLoc Loc, StringRef Name) {
    ProcedureDeclaration *P =
    new ProcedureDeclaration(CurrentDecl, Loc, Name);
    if (!CurrentScope->insert(P))
        Diags.report(Loc, diag::err_symbold_declared, Name);
    return P;
}
\end{cpp}

真正的工作是在所有声明和过程解析之后完成的。只需要检查过程声明末尾的名称是否与过程名称相等，以及用于返回类型的声明是否为类型声明:

\begin{cpp}
void Sema::actOnProcedureDeclaration(
        ProcedureDeclaration *ProcDecl, SMLoc Loc,
        StringRef Name, FormalParamList &Params, Decl *RetType,
        DeclList &Decls, StmtList &Stmts) {

    if (Name != ProcDecl->getName()) {
        Diags.report(Loc, diag::err_proc_identifier_not_equal);
        Diags.report(ProcDecl->getLocation(),
                     diag::note_proc_identifier_declaration);
    }
    ProcDecl->setDecls(Decls);
    ProcDecl->setStmts(Stmts);

    auto *RetTypeDecl =
    dyn_cast_or_null<TypeDeclaration>(RetType);
    if (!RetTypeDecl && RetType)
        Diags.report(Loc, diag::err_returntype_must_be_type, Name);
    else
        ProcDecl->setRetType(RetTypeDecl);
}
\end{cpp}

有些声明本身就存在，不能由开发人员定义。这包括BOOLEAN和INTEGER类型以及TRUE和FALSE字面值，这些声明存在于全局作用域中，必须以编程方式添加。Modula-2还预定义了一些程序，如INC或DEC，可以添加到全局作用域。对于我们的类，初始化全局作用域很简单:

\begin{cpp}
void Sema::initialize() {
    CurrentScope = new Scope();
    CurrentDecl = nullptr;
    IntegerType =
        new TypeDeclaration(CurrentDecl, SMLoc(), "INTEGER");
    BooleanType =
        new TypeDeclaration(CurrentDecl, SMLoc(), "BOOLEAN");
    TrueLiteral = new BooleanLiteral(true, BooleanType);
    FalseLiteral = new BooleanLiteral(false, BooleanType);
    TrueConst = new ConstantDeclaration(CurrentDecl, SMLoc(),
                                        "TRUE", TrueLiteral);
    FalseConst = new ConstantDeclaration(
        CurrentDecl, SMLoc(), "FALSE", FalseLiteral);
    CurrentScope->insert(IntegerType);
    CurrentScope->insert(BooleanType);
    CurrentScope->insert(TrueConst);
    CurrentScope->insert(FalseConst);
}
\end{cpp}

使用该方案，tinylang所需的所有计算都可以完成。例如，下面来看看如何计算表达式的结果是否为常量:

\begin{itemize}
\item
必须确保常量声明的字面量或引用是常量

\item
表达式的两边都是常量，运算符也会得到一个常量
\end{itemize}

为表达式创建AST节点时，这些规则被嵌入到语义分析器中，也可以计算类型和常数值。

但并不是所有种类的计算都可以用这种方法进行。例如，要检测未初始化变量的使用，可以使用一种称为符号解释的方法。该方法需要一个特殊的遍历AST的顺序，在构造期间不可能获取。好消息是，所提出的方法创建了一个完全修饰过的AST，可以为代码生成做好准备。这个AST可以用于进一步的分析，所以昂贵的分析可以根据需要打开或关闭。

要使用前端，还需要更新驱动程序。由于缺少代码生成，正确的tinylang程序不会产生任何输出。尽管如此，其仍可以用于探索错误恢复和引发语义错误:

\begin{cpp}
#include "tinylang/Basic/Diagnostic.h"
#include "tinylang/Basic/Version.h"
#include "tinylang/Parser/Parser.h"
#include "llvm/Support/InitLLVM.h"
#include "llvm/Support/raw_ostream.h"

using namespace tinylang;

int main(int argc_, const char **argv_) {
    llvm::InitLLVM X(argc_, argv_);

    llvm::SmallVector<const char *, 256> argv(argv_ + 1,
                                              argv_ + argc_);
    llvm::outs() << "Tinylang "
                 << tinylang::getTinylangVersion() << "\n";

    for (const char *F : argv) {
        llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
            FileOrErr = llvm::MemoryBuffer::getFile(F);
        if (std::error_code BufferError =
                FileOrErr.getError()) {
            llvm::errs() << "Error reading " << F << ": "
                         << BufferError.message() << "\n";
            continue;
        }

        llvm::SourceMgr SrcMgr;
        DiagnosticsEngine Diags(SrcMgr);
        SrcMgr.AddNewSourceBuffer(std::move(*FileOrErr),
                                  llvm::SMLoc());
        auto TheLexer = Lexer(SrcMgr, Diags);
        auto TheSema = Sema(Diags);
        auto TheParser = Parser(TheLexer, TheSema);
        TheParser.parse();
    }
}
\end{cpp}

恭喜!已经完成了tinylang的前端实现!可以使用示例程序Gcd.mod(在定义真正的编程语言一节中提供)，以运行前端:

\begin{shell}
$ tinylang Gcd.mod
\end{shell}

这是一个有效的程序，看起来好像什么也没发生。一定要尝试修改代码文件，使它输出一些错误消息。我们将在下一章中添加代码生成的过程。
